package bsea.bstree;

import java.util.Stack;

public class BinaryTree {
	 private Node root = null;  
     
	    BinaryTree(int value) {  
	        root = new Node(value);  
	        root.leftChild  = null;  
	        root.rightChild = null;  
	    }  
//	    	public Node findKey(int value) {}   //查找  
//	        public String insert(int value) {}  //插入  
//	        public void inOrderTraverse() {}    //中序遍历递归操作  
//	        public void inOrderByStack() {}     //中序遍历非递归操作      
//	        public void preOrderTraverse() {}  //前序遍历  
//	        public void preOrderByStack() {}   //前序遍历非递归操作  
//	        public void postOrderTraverse() {} //后序遍历  
//	        public void postOrderByStack() {}  //后序遍历非递归操作  
//	        public int getMinValue() {} //得到最小(大)值  
//	        public boolean delete(int value) {} //删除 
	        
	        public Node findKey(int value) {  
	            Node current = root;  
	            while (true) {  
	                if (value == current.value) {  
	                    return current;  
	                } else if (value < current.value) {  
	                    current = current.leftChild;  
	                } else if (value > current.value) {  
	                    current = current.rightChild;  
	                }  
	                  
	                if (current == null) {  
	                    return null;  
	                }  
	            }  
	        }
	        
	        
	        public String insert(int value) {
	    		String error = null;
	    		Node node = new Node(value);
	    		if (root == null) {
	    			root = node;
	    			root.leftChild  = null;
	    			root.rightChild = null;
	    		} else {
	    			Node current = root;
	    			Node parent = null;
	    			while (true) {
	    				if (value < current.value) {
	    					parent = current;
	    					current = current.leftChild;
	    					if (current == null) {
	    						parent.leftChild = node;
	    						break;
	    					}
	    				} else if (value > current.value) {
	    					parent = current;
	    					current = current.rightChild;
	    					if (current == null) {
	    						parent.rightChild = node;
	    						break;
	    					}
	    				} else {
	    					error = "having same value in binary tree";
	    				}	
	    			} // end of while
	    		}
	    		return error;
	        }
	        
	        
	        /**
	    	 * //前序遍历(递归)：
	    	 *    1、访问这个节点
	    	 *    2、调用自身来遍历节点的左子树
	    	 *    3、调用自身来遍历节点的右子树
	    	 */
	    	public void preOrderTraverse() {
	    		System.out.print("前序遍历:");
	    		preOrderTraverse(root);
	    		System.out.println();
	    	}
	    	
	    	private void preOrderTraverse(Node node) {
	    		if (node == null) 
	    			return ;
	    		
	    		node.display();
	    		preOrderTraverse(node.leftChild);
	    		preOrderTraverse(node.rightChild);
	    	}
	    	
	    	
	    	  /**
	    	 * //中序遍历(递归)：
	    	 *    1、调用自身来遍历节点的左子树
	    	 *    2、访问这个节点
	    	 *    3、调用自身来遍历节点的右子树
	    	 */
	    	public void inOrderTraverse() {
	    		System.out.print("中序遍历:");
	    		inOrderTraverse(root);
	    		System.out.println();
	    	}
	    	
	    	private void inOrderTraverse(Node node) {
	    		if (node == null) 
	    			return ;
	    		
	    		inOrderTraverse(node.leftChild);
	    		node.display();
	    		inOrderTraverse(node.rightChild);
	    	}
	    	
	    	
	    	  public int getMinValue() {
	    			Node current = root;
	    			while (true) {
	    				if (current.leftChild == null)
	    					return current.value;
	    				
	    				current = current.leftChild;
	    			}
	    		}
	        
	        public static void main(String[] args){
	        	BinaryTree btree=new BinaryTree(8);
	        	btree.insert(6);
	        	btree.insert(5);
	        	System.out.println(btree.root.value);
	        	System.out.println(btree.root.leftChild.value);
	        }

}
